由题显然有：
顺带一提， 是 换根dp 的基操。
因为我们知道 , 所以考虑将 消掉，从而确定父子关系。
化简可得：
可以发现， 最大的节点一定是叶子，并且对于叶子 的父亲的 ，满足
那么可以把 从大到小排序，维护对父亲的贡献即可。
注意我们构造出的这棵树只满足父子 的差值，所以还要遍历这棵树判断根的 是否与题目相同。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long
const int MAXN = 1e6;
int n , fa[ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];
struct node {
int id; LL d , f;
bool operator < ( const node &x ) const { return d > x.d; }
bool operator > ( const node &x ) const { return d < x.d; }
bool operator > ( const LL &x ) const { return d < x; }
bool operator < ( const LL &x ) const { return d > x; }
}p[ MAXN + 5 ];
int rt; LL disrt;
void dfs( int u , int dep ) {
disrt += dep;
for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) dfs( Graph[ u ][ i ] , dep + 1 );
}
int main( ) {
scanf("%d",&n);
for( int i = 1 ; i <= n ; i ++ ) scanf("%lld",&p[ i ].d) , p[ i ].id = i;
sort( p + 1 , p + n + 1 );
for( int i = 1 ; i < n ; i ++ ) {
fa[ i ] = lower_bound( p + 1 , p + n + 1 , p[ i ].d + 2 - n + p[ i ].f ) - p;
if( fa[ i ] == n + 1 ) return printf("-1\n") & 0;
Graph[ fa[ i ] ].push_back( i );
p[ fa[ i ] ].f += p[ fa[ i ] ].d + n - p[ i ].d;
}
for( int i = 1 ; i <= n ; i ++ ) if( !fa[ i ] ) rt = i;
dfs( rt , 0 ); if( disrt != p[ rt ].d ) return printf("-1\n") & 0;
for( int i = 1 ; i < n ; i ++ ) if( fa[ i ] ) printf("%d %d\n", p[ fa[ i ] ].id , p[ i ].id );
return 0;
}